package offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class offer38 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "abc";
        System.out.println(solution.permutation(s));
    }

    static class Solution {
//        List<String> list = new ArrayList<>();
        StringBuffer res = new StringBuffer();
        StringBuffer sb = new StringBuffer();
        boolean[] used;
        public String permutation(String s) {
            if(s == null || s.length() == 0){
                return "";
            }
            used = new boolean[s.length()];
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            dfs(arr, 0);
//            return list.toArray(new String[list.size()]);
            return res.toString();
        }
        public void dfs(char[] arr, int row){
            if(row == arr.length){
                res.append(sb.toString()+",");
                return;
            }
            for(int i = 0; i < arr.length; i++){
                if(used[i]) continue;
                if(i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue;
                sb.append(arr[i]);
                used[i] = true;
                dfs(arr, row+1);
                used[i] = false;
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}
